package Test1;

import java.time.Clock;
import java.util.Arrays;
import java.util.Random;

class Test {

     static Object[] s1 = new Object[12];
     static Object[] s2 = new Object[12];
     static Object[] s3 = new Object[12];
     static Object[] s4 = new Object[12];
     static Object[] s5 = new Object[12];
    public static void main(String[] args) {
        int i=0;
        long n;
        while(i<12){
            i++;
            System.out.println("===================the "+ i +" time======================");
        int[] arr = new int[10000*i];
        int[] a =getRandomArr(arr);
        int[] b = a.clone();
        int[] d = b.clone();
        int[] g = b.clone();
        int[] h = b.clone();

        long s = Clock.systemDefaultZone().millis();
        quickSort(a, 0, a.length - 1);
        n=(Clock.systemDefaultZone().millis() - s);
        s1[i-1]= (int) n;
        System.out.println("quickSort  : " + n + " ms");

        s = Clock.systemDefaultZone().millis();
        mergeSort(b,0,b.length-1);
            n=(Clock.systemDefaultZone().millis() - s);
            s2[i-1]= (int) n;
        System.out.println("mergeSort  : " + (Clock.systemDefaultZone().millis() - s) + " ms");


        s = Clock.systemDefaultZone().millis();
        arraysSort(d);
            n=(Clock.systemDefaultZone().millis() - s);
            s3[i-1]= (int) n;
        System.out.println("arraysSort : " + (Clock.systemDefaultZone().millis() - s) + " ms");


        s = Clock.systemDefaultZone().millis();
        InsertSort(g);
            n=(Clock.systemDefaultZone().millis() - s);
            s4[i-1]= (int) n;
        System.out.println("insertSort : " + (Clock.systemDefaultZone().millis() - s) + " ms");

        s = Clock.systemDefaultZone().millis();
        selectSort(h);
            n=(Clock.systemDefaultZone().millis() - s);
            s5[i-1]= (int) n;
        System.out.println("selectSort : " + (Clock.systemDefaultZone().millis() - s) + " ms");

        }
    }

    private static int[] getRandomArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(arr.length);
        }
        return arr;
    }


        public static void InsertSort(int[] arr) {
            if (arr.length >= 2) {
                for (int i = 1; i < arr.length; i++) {
                    //挖出一个要用来插入的值,同时位置上留下一个可以存新的值的坑
                    int x = arr[i];
                    int j = i - 1;
                    //在前面有一个或连续多个值比x大的时候,一直循环往前面找,将x插入到这串值前面
                    while (j >= 0 && arr[j] > x) {
                        //当arr[j]比x大的时候,将j向后移一位,正好填到坑中
                        arr[j + 1] = arr[j];
                        j--;
                    }
                    //将x插入到最前面
                    arr[j + 1] = x;
                }
            }

    }
    public static void quickSort(int[] arr,int begin,int end) {
        //先定义两个参数接收排序起始值和结束值
        int a = begin;
        int b = end;
        //先判断a是否大于b

        if (a >= b) {
            //没必要排序
            return;
        }
        //基准数,默认设置为第一个值
        int x = arr[a];

        //循环
        while (a < b) {
            //从后往前找,找到一个比基准数x小的值,赋给arr[a]
            //如果a和b的逻辑正确--a<b ,并且最后一个值arr[b]>x,就一直往下找,直到找到后面的值大于x
            while (a < b && arr[b] >= x) {
                b--;
            }
            //跳出循环,两种情况,一是a和b的逻辑不对了,a>=b,这时候排序结束.二是在后面找到了比x小的值
            if (a < b) {
                //将这时候找到的arr[b]放到最前面arr[a]
                arr[a] = arr[b];
                //排序的起始位置后移一位
                a++;
            }

            //从前往后找,找到一个比基准数x大的值,放在最后面arr[b]
            while (a < b && arr[a] <= x) {
                a++;
            }
            if (a < b) {
                arr[b] = arr[a];
                //排序的终止位置前移一位
                b--;
            }
        }
        //跳出循环 a < b的逻辑不成立了,a==b重合了,此时将x赋值回去arr[a]
        arr[a] = x;
        //调用递归函数,再细分再排序
        quickSort(arr,begin,a-1);
        quickSort(arr,a+1,end);
    }

    public static void selectSort(int[] arr){
        for(int i = 0; i < arr.length - 1 ; i++){
            int min = i; // 遍历的区间最小的值
            for (int j = i + 1; j < arr.length ;j++){
                if(arr[j] < arr[min]){
                    // 找到当前遍历区间最小的值的索引
                    min = j;
                }
            }
            if(min != i){
                // 发生了调换
                int temp =  arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void mergeSort(int[] a,int s,int e){
        int m = (s + e) / 2;
        if (s < e){
            mergeSort(a,s,m);
            mergeSort(a,m+1,e);
            merge(a,s,m,e);
        }
    }

    private static void merge(int[] a, int s, int m, int e) {

        int[] temp = new int[(e - s) + 1];
        //左起始指针
        int l = s;
        //右起始指针
        int r = m+1;
        int i = 0;

        while (l <= m && r <= e){
            if (a[l] < a[r]){
                temp[i++] = a[l++];
            }else{
                temp[i++] = a[r++];
            }
        }

        while (l <= m){
            temp[i++] = a[l++];
        }
        while (r <= e){
            temp[i++] = a[r++];
        }

        for (int n = 0; n < temp.length; n++) {
            a[s+n] = temp[n];
        }

    }

    private static void arraysSort(int[] a){
        Arrays.sort(a);
    }





}
